Lịch sử Aceh thời cổ không rõ ràng. Tiếng Aceh là một trong mười ngôn ngữ thuộc nhóm ngôn ngữ Aceh-Chăm. Theo Sejarah Melayu, vua Chăm Pa Syah Pau Kubah có một con trai tên Syah Pau Ling, người đã chạy thoát khỏi thủ đô Vijaya khi nó bị quân đội nhà Lê của Đại Việt đánh chiếm năm 1471. Syah Pau Ling sau đó đã lập nên Aceh.

Hồi quốc này được thành lập bởi Ali Mughayat Syah, người đã mở rộng quyền lực ra khắp bắc Sumatra năm 1520.[1] Ông đánh chiếm Deli, Pedir, Pasai, và tấn công Aru. Con trai ông, Alauddin al-Kahar tuy mở rộng lãnh thổ ra xa hơn về phía nam của Sumatra, song lại ít thành công hơn trong việc tìm chỗ đứng trong khu vực eo biển, mặc dù đã nhiều lần tấn công cả Johor và Malacca[2] với sự hỗ trợ về người và hỏa lực từ sultan Suleiman I của đế quốc Ottoman.[3]

Ngày 21 tháng 6, 1599, thuyền trưởng người Hà Lan Cornelius Houtman cập bến "Acheen", đây là một trong ba chuyến viễn chinh đầu tiên tới Đông Ấn. Thủy thủ đoàn ở lại đây ba tháng để tìm lấy hồ tiêu và các gia vị khác. John Davis nói rằng sau đó nhóm của ông đã bị chủ đất địa phương tấn công, với tổng cộng 68 người chết và bị bắt. Sau khi đến, họ được sultan cho phép thu mua hồ tiêu. Cùng năm đó, đại diện của Công ty Đông Ấn Anh dưới sự chỉ huy của James Lancaster đến Aceh. Lancaster trở lại năm 1602, mang theo lá thư của nữ hoàng Elizabeth I.[4][5]

Sultan từ năm 1589 đến 1604 là Alauddin Riayat Shah ibn Firman Shah. Sau khi ông mất, mâu thuẫn nội bộ khiến đất nước không có một vị quân chủ nào đủ sức quản lý. Năm 1607, Iskandar Muda lên ngôi. Iskandar Muda mở rộng bờ cỏi ra phần lớn Sumatra. Ông cũng chinh phục Pahang, một vùng sản xuất thiếc trên bán đảo Mã Lai, và đã buộc sultan của Johor phải công nhận vị thế nước lớn của mình. Ông còn ban hành luật Adat Meukuta Alam (Adat có nghĩa là "phong tục"). Đội thủy quân của ông đã phải chịu kết cục thảm hại trong một chiến dịch tiến đánh Malacca năm 1629, khi thủy quân hợp lực giữa Johor và Bồ Đào Nha đã phá tan toàn bộ tàu thuyền và tiêu diệt 19.000 quân Aceh.[5][6][7] Tuy vậy, Aceh vẫn có thể chinh phục Kedah trong cùng năm đó và kết nạp thêm nhiều thần dân mới.[7] Con rể ông, Iskandar Thani, cựu hoàng tử Pahang, trở thành người nói ngôi. Trong thời kỳ này, Aceh chú trọng củng cố nội bộ và thống nhất về tôn giáo.

Sau Iskandar Thani, Aceh được cai trị bởi nhiều nữ sultan. Chính sách bắt con tin từ các vương quốc bị chinh phục của Aceh[7] khiến họ khao khát tìm sự độc lập, kết quả là quyền lực của Aceh bị suy yếu khi những thuộc vương mỗi lúc một có thêm quyền lực. Tước vị "Sultan" dần trở thành một danh hiệu chỉ còn tính biểu tượng.[8] Tới thập niên 1680, một người Ba Tư đã mô tả bắc Sumatra là nơi "mỗi góc lại có một vị vua hay một thống sứ hoặc nhà lãnh đạo tự quản lý một cách độc lập và không và không cống nạp bất cứ gì cho cấp cao hơn."[9]